339. Опять несократимые
Дробь m/n
называется правильной несократимой, если 0 < m < n и НОД (m, n)
= 1. Найдите количество правильных несократимых дробей со знаменателем n.
Вход. Каждая строка является отдельным тестом и содержит число n (n
< 109). Последняя строка содержит 0 и не обрабатывается.
Количество тестов не больше 100.
Выход. Для каждого значения
n в отдельной строке выведите количество
правильных несократимых дробей со знаменателем n.
|
Пример
входа |
Пример
выхода |
|
12 123456 7654321 0 |
4 41088 7251444 |
РЕШЕНИЕ
теория
чисел
Анализ алгоритма
Количество
правильных несократимых дробей p / n (со знаменателем n) равно количеству
таких натуральных чисел p, что p < n и p взаимно просто
с n. Такое количество чисел p равно функции
Эйлера j(n).
Пример
При n = 12 имеются j(12) = 4 правильные несократимые дроби:
Реализация алгоритма
Функция euler вычисляет значение j(n).
int euler(int n)
{
int i, result = n;
for (i = 2; i * i <= n; i++)
{
if (n % i == 0) result -= result / i;
while (n % i == 0) n /= i;
}
if (n > 1) result -= result / n;
return result;
}
Основная часть
программы. Читаем входное значение n
и выводим j(n).
while(scanf("%d",&n),n)
printf("%d\n",euler(n));
Java реализация
import
java.util.Scanner;
public class Main
{
static int
euler(int n)
{
int result = n;
for(int i = 2;
i * i <= n;i++)
{
if (n % i ==
0) result -= result / i;
while (n % i ==
0) n /= i;
}
if (n >
1) result -= result / n;
return result;
}
public static void
main(String[] args)
{
Scanner con = new
Scanner(System.in);
while(con.hasNext())
{
int n = con.nextInt();
if (n ==
0) break;
System.out.println(euler(n));
}
con.close();
}
}
import math
Функция euler вычисляет
значение j(n).
def euler(n):
result = n
i = 2
while i <= math.isqrt(n):
if n % i == 0:
result -= result // i
while
n % i == 0: n //= i
i += 1
if n > 1: result -= result // n
return result
Основная часть программы. Читаем входное значение n и выводим j(n).
while True:
n = int(input())
if n == 0: break
print(euler(n))